//
// Created by fan on 2020/6/30.
//
#include <iostream>
#include <vector>
using namespace std;

bool  t(int a,int b){return a<b;}
class Solution {
public:
    int hammingDistance(int x, int y) {
        int temp = x ^ y;
        int count = 0;
        while (temp!=0) {
            ++count;
            temp &= temp - 1;
        }

        return count;
    }
    /*
    int totalHammingDistance(vector<int>& nums) {
        int ss = nums.size();
        //sort(nums.begin(),nums.end(),t);
        int count = 0;
        for(auto i=0;i<ss;i++){
            for(auto x=i+1;x<ss;x++){
                count = count+hammingDistance(nums[i],nums[x]);
            }

        }
        return count;
    }*/
    int totalHammingDistance(vector<int>& nums)
    {
        if (nums.empty())
            return 0;

        int ans = 0, n = nums.size();
        vector<int> cnt(32, 0);         // count of elements with a particular bit ON

        for (auto num : nums) {         // loop over every element
            int i = 0;
            while (num > 0) {           // check every bit
                cnt[i] += (num & 0x1);
                num >>= 1;
                i++;
            }
        }

        for (auto&& k : cnt) {           // loop over every bit count
            ans += k * (n - k);
        }

        return ans;
    }
};
//
//int main()
//{
//    vector<int> nums = {594783340,134702242,78774512,551770141,766372041,955462028,360570908,63882569,518470839,243730125,120896046,173293638,351327112,115204359,795369275,833185997,409168070,645114796,946926316,782263673,610665177,625280826,457357811,761735442,130532505,717481457,590169894,905926612,42489232,944929998,589885399,64881372,687010175,353419884,135706433,776343473,687090117,904026500,526582975,499951538,729472102,46456169,45247100,844755818,589621387,70082629,496180556,627603391,838002120,896852392,3412629,166975712,747148602,782648383,427013784,723297992,711909524,77467362,618863052,968012543,50700529,720266691,949936076,182197534,675251894,654991710,237474026,994317434,568350862,265675778,594298733,432363334,793376737,349833114,627900090,382171272,28980327,741051667,243193247,687522088,721712156,621546214,759738268,776283792,38536619,85356364,651290708,311759175,669334123,979262275,146385317,429247004,749804533,323724113,48067918,9603710,934237601,123911721,672640904,514734298,868194948,394088249,601633595,302821089,770778011,844672173,538304941,735517154,920935146,242354893,275186870,533432099,442040246,224479549,491990842,78040544,307893269,474066460,263641428,555695213,956042666,736440608,409040995,449827496,901266410,27885510,520331524,658513284,649531197,804428856,271719858,245419884,248883079,827248044,541723408,207633554,36215703,939448220,6460796,5394600,58686182,82140410,849369496,822296241,68632620,895683057,677752107,726398661,137762232,382461758,616211235,496080811,891651401,637186419,484175122,715736971,335364750,123758453,244149275,368594086,617965454,707447064,238829787,365293866,985742736,334805925,676026335,786119715,787632239,438819343,570832581,966716296,532492248,32855087,85128508,323703632,703843751,954973959,747529813,954232141,371717991,434345614,749818345,762883819,310973343,346757581,831529556,486651594,535612582,582196028,33146864,694057253,682059245,102023029,9098097,233355920,500786596,524884957,671629001,894571175,524725578,494934864,959072995,920551161,231169939,268225928,297975421,934014521,24078524,399300741,161157112,590702517,120303138,152728539,458575386,750681997,245897454,39972550,449244917,54300814,539188079,546031991,962049106,754946279,48724677,517355410,824067745,984550712,982316449,85763854,57524197,27494985,985185946,714254630,836958258,739554356,54712456,429247076,958036059,27142054,348441923,75494492,820575314,62299942,43567683,536081710,24379383,160870660,864249625,11542714,163339477,762489073,118928262,313002655,448171082,979203723,102764078,17480267,733071477,411609678,672009737,644128764,200050599,84004769,971396504,90358234,172878987,824738696,523805934,863842263,252955452,552144351,406247148,738281201,924611419,752449441,34041351,340809664,649136299,816850533,91436507,761039053,370762239,550890926,814769643,123151560,781516859,736842739,370700702,516638567,868010748,800227565,882087441,956984224,174315316,549821504,227884687,94591808,459596854,738625497,623248419,303926645,379009949,376694419,114287355,770173645,70005977,916900530,797535416,732295785,259456116,80116780,636431947,688666100,621769017,209420995,805944110,323295141,280786455,949355304,804075696,133115748,184373618,741473683,100586640,490028291,305700592,128966120,515557595,672962098,825095984,879272987,899096080,58371199,792198561,875581905,347128091,261735116,935585556,511176358,406460906,35944613,471184462,70541276,176252588,897297303,245602287,167046653,584948920,849341052,551259355,771526327,536717303,176394121,921537365,419409969,774998107,697843872,46739015,149567459,17395001,885962971,521023877,557471920,752386157,970427163,978513223,234948813,355251836,713068992,591798284,2484862,960886341,539707747,44662548,610124942,135485769,776653763,814188275,296539241,772962447,844244604,587582277,11015564,454990506,983651022,686590726,893675129,290244563,997986582,106179182,580558373,71861621,892454533,457545483,620971452,44152991,635935031,133954898,817108630,134305492,853048203,373299027,29992480,10911471,645961680,941098753,622660094,153366605,445132413,300417721,386582750,158247075,866813117,791974749,615962337,607819419,834244932,233840861,268276817,360288266,253980700,603618311,93183127,406215404,204759793,922017035,891289071,196978472,137857455,421348228,139062415,198274478,652015249,604217880,787226144,56031619,918561725,799952370,551852370,793889775,589549614,70815240,485798242,78227400,507919836,361186827,678214967,708730671,692081235,830863071,22456434,615648013,412921823,102910635,894706610,653497976,109111874,685210358,523171692,941555204,704297463,197598377,26203977,969072382,683545426,457946979,926463783,820360131,740686555,549206804,634040022,496793340,189245844,231618901,578500743,996496210,679817095,72913625,39111516,217253430,656198110,393107425,89772381,709360782,544938577,557887762,506013132,527467404,332164212,373912531,603735973,923244714,404558623,276528937,260210629,876314889,574466875,771269791,520084045,794101025,992544717,839067301,826501705,882905717,677363427,636304842,54401081,76891901,330003191,560854583,770228376,989869894,187495149,872459094,401651142,9641073,769218964,204551586,570165633,701760917,515542695,777042867,704386840,345252547,158743235,822861071,31333617,490607404,448918195,651030032,225544937,218097782,607815223,118227829,71222037,880384480,459627530,461218451,430023934,922765161,580140871,851861517,110525317,611605320,39373629,327619327,149957981,345468736,290243042,179444557,650607689,569677077,80534813,426883059,673686564,116294164,138874156,536194181,974217255,254080057,919006341,830162541,133550606,257602505,991247761,870469348,112707050,772769852,754784086,470230573,425419451,51652094,326329048,732053876,695680269,397306815,801959760,723296326,329403993,80068385,384583673,564993219,815828346,736903705,602377686,923856644,951847898,101935183,325648953,393620515,123341423,116050515,545854129,120206119,669613853,31212022,594443886,724466158,17922663,16959970,578374386,20297758,280475989,26320536,780595848,496817813,600563555,498527985,426136948,18700869,565871399,188509008,732518131,55963113,560159961,833134657,900801759,15452163,6465901,736689266,293268707,285167262,415650908,80507065,167543845,558341698,692864543,111018745,314715128,957912313,94826679,905085035,930490122,564541578,460527578,348918236,283931073,320880277,703377922,922741966,190302506,811067959,540479404,774494796,35651905,846608400,868217425,771859188,836144836,746251262,940461954,864418958,562555151,641408763,582150379,265924121,473232240,482312839,274096226,382847567,658052157,341820649,460892018,238631797,332643230,627812047,842894796,376195691,529121869,221470056,658070941,657523337,43877497,862201158,942696197,553613991,691187933,849521886,88547677,14639968,240806418,19771309,583908725,546652863,659626575,33260211,451596635,570414525,382900045,185544834,305769594,141199087,163625274,270911958,344925044,889829833,86864101,429044125,842005896,468838920,658227597,142957082,438454759,92741656,428863248,949489804,124154971,465976360,584800489,856649951,778335547,955623130,920728575,65483390,506181975,217728058,836314896,663987457,312159987,963330466,815927329,607532408,305418349,680275313,184248963,902167,130335240,111058740,400953937,29134873,43538995,615448985,215341874,740931123,719198955,184366300,972985126,666019355,102531321,755005731,693429372,73702935,774647873,106428328,34514392,848758810,148431227,455118022,624823718,217194596,814858719,620251892,480904884,232916658,915066172,32251568,886224332,973255979,923278432,971257049,687000274,187013777,371974478,243133907,483173286,57748495,709325599,953617896,785520511,661250268,198359629,728643037,144746243,237091206,2712635,80057014,631944785,789367080,531520972,888488531,18437857,647417431,992607115,887790487,171314231,295688368,357241818,946441761,228282376,129078468,49285362,996348548,700050577,480124304,353115549,108693960,896759279,792967507,121376867,19022666,324841215,495848409,133154634,251973464,80257564,269147832,967051842,84067998,679581238,403832320,954456298,637135974,990851076,645835494,967774298,134462686,554545536,960774150,801597257,280180768,359508483,387574770,444236617,277159878,334039203,674631563,966506828,306930866,124323346,793866269,194484272,227048770,77720318,13800759,21122637,673358304,41679285,10031229,529614846,64483554,881807499,753987746,118529722,850170394,605108467,368431255,28748484,784928591,302785416,525726969,938422803,745125031,132228938,312143477,685846896,484047623,513323503,779283500,708000025,149532148,630944446,9055036,864134762,874018851,846683277,979191517,104639258,675880891,489126054,967167440,879439937,764562505,252856465,35953489,265858325,514882515,64310773,686887370,791424965,758655815,117870466,861978106,134323458,362024187,512317536,51865307,407811223,108402315,851575549,599228435,326981193,162258078,914768903,478502426,656994345,890527188,69891351,576338504,15483689,388839736,436705131,751514918,5393750,458443076,28936543,443647488,320108432,615880889,238922883,929958338,216782478,123821012,734051897,709659442,122066256,720681707,689680469,490399624,897221960,126796133,197303016,357038944,684222090,93220592,681384590,647998326,811269723,429538236,202089816,351891605,865219975,140345988,650954488,103360576,452887565,792238565,547929133,428038573,767057539,591725032,125843567,928921921,977591135,124306395,301949390,152518447,75042789,671253934,33271047,633717287,160532067,822989437,41297332,447040943,519331795,828915735,653318634,35373105,455784094,289099009,279034749,425719973,807558054,324543116,780665810,672669147,989414399,914903850,599073008,9686898,184894670,908860059,159830502,916688364,526628748,62236927,777453156,10179475,435228212,344235980,46149420,184683951,662273120,209564017,62231217,888506608,676763065,76417521,740011697,91770280,75794570,7492475,810449308,880230282,808483969,61032414,67577410,902164254,85564089,409083980,24792744,79820890,519902502,683370049,657869387,564972553,113989815,271407581,291947639,911318925,476780649,783859364,305134981,212676631,43348609,356093708,623004745,857970090,343591603,160544838,37631634,907658998,93929676,275583987,765326577,209712687,620465682,133611189,921315917,199522149,939763854,661849071,879528484,898266865,154140223,562428257,301679883,124903014,153433179,416557984,293347868,822647611,531657269,677243494,768074558,504894189,48745226,862722453,759661605,842313820,556171716,729199068,752541025,425809992,966002318,417565884,846232570,994093556,100600610,517800659,864916747,131938864,86342122,39056238,81174662,650428389,58170693,362756444,934459053,905393260,22881825,761217118,8995625,304087594,936596145,109255083,944640374,224163547,830417591,332230084,333539588,867536846,425291239,837255235,81374432,860479132,710871204,953775945,87344985,714305503,899002191,982367492,589138486,396416463,77220647,560269919,533715116,110761093,840851749,398443114,779405652,968030111,138944483,718180070,239835281,84762348,819124875,661596855,580996397,198301470,105669793,609192038,281532348,807698495,744472778,114252424,183088328,614441123,810579485,566126405,533932625,264446140,402609337,727133840,756497450,142430488,970902567,378693663,355842911,57331929,943530356,895443844,159287932,387648962,543697914,387922613,55004399,40965783,110126419,349777575,841939764,504842043,965305982,806170036,618444707,172317647,127715551,617575813,808223140,972246705,347300912,225875438,684882217,96051777,227492073,938379251,220167989,249067342,629188991,569893909,429862943,571494493,561074467,170851470,107998829,305615866,497954816,382820153,197305059,391375645,108054754,452568763,729100645,452850733,380224563,670380516,31615181,927886258,105577339,55317660,10976116,377945126,660083434,121754836,929096708,767752597,181641534,274999551,325623891,765382059,142198661,576574894,48028194,548983864,182054736,422729555,939726609,390377425,303818968,362261188,407647471,858211167,454910517,432254477,756795716,67441278,200150886,769528378,109905390,929910466,412197774,25742396,8236525,785300845,909786031,690256377,432267145,176728214,301208897,798975900,172706609,429570366,742098726,15749753,4083599,61055336,245806042,296589644,472602021,627640341,104515701,746742039,599016405,265381699,94163921,503529564,381307899,550655845,365751992,888510408,386124596,47987385,656085579,649282555,920470056,661016782,776149143,922974523,158425780,575340758,780740912,580403392,762063248,197517006,451580158,500507008,327838157,680350144,87428511,532169829,56409895,479290447,223382832,593842468,353852067,602450104,786480901,622655822,288588523,289231135,145171362,939615298,312552026,316900420,385914380,662370720,56948639,944026267,640285433,236717314,368182154,930053849,674552208,632787343,917853857,994738198,404701891,743971988,287409482,593420449,496408253,952518154,629509540,307888589,395409700,129402660,55529365,67113335,130863826,991026210,87323916,714703889,945203330,888809029,110080449,931664854,980909479,706634112,814952474,255529952,872092911,482642980,527808719,419173054,295156418,799671334,123447612,107790460,98525377,792076558,972561131,336891400,12361239,596913761,78960921,98789048,928627761,328611309,789813926,599210753,29799819,481868182,597702037,797118840,966332472,524013221,259769000,103328649,477816967,21386814,256887358,63695436,875315224,952966396,366156824,102587244,901925014,359624703,193400663,135163708,244698986,17652275,122021217,756689812,287512750,388583500,425113973,212450642,540118780,155938169,715735621,105653878,341708633,518701331,970125522,996778808,134474387,751204243,226329966,527178303,561189577,165043015,476564828,304039464,127675235,294489870,334417333,587411532,643293065,393864457,928307323,385460784,274212267,185665007,178033558,765289035,933249362,48953093,854354406,851816378,144852722,879200112,28791024,145393302,936320075,764313887,723806102,307274637,814136671,222209391,199172404,711072002,33620637,66825476,794806329,961687163,114221219,658625893,394667013,384480486,185234379,530403350,77463331,344092613,784063898,802275694,945253192,579356016,545705414,915720408,290577785,363019217,262938992,841776665,911120797,648832069,791602795,806982400,593965995,75465287,768200388,472235352,907485399,471218577,643912081,60248134,918568979,921870348,927909378,139650110,692751177,560181452,194333894,640107949,548711020,684311500,93945746,545672477,362148249,449943923,710571352,209130675,221503164,214517097,556784544,291581029,837650527,637101204,199450264,731592659,533940738,400801331,759253125,212419979,817744317,726373597,863995231,676404981,707572096,192758964,294568272,652119747,213032119,575584484,582076500,964701993,37840079,116026819,940574035,600680678,319530599,641659893,507924995,447894140,826628245,69201272,70104055,856287338,333371219,978221288,977869631,155516304,67901507,699790170,398431149,578309897,143452557,530473565,110083189,184737456,414048008,57854176,338022519,50230518,56221333,812117629,2413918,354487689,547930823,456442403,408858715,533731183,380799162,590247674,65691425,62163995,906190101,175981561,430092386,925754278,633127831,197984732,77221521,574959237,456463337,967717875,540666394,769752079,574680803,71790393,842809184,84798454,71453348,473061163,754505347,80431494,44905695,756234346,15408854,717045047,845361612,33782910,646664140,862442091,697089834,111040584,95806045,746946712,536966800,74722906,382926225,980057163,414144629,327258254,316833589,55664341,395192742,630473201,678774909,736762699,379973491,745580706,200824075,198914019,663362601,193118361,892502710,119772675,827171486,609518171,467882385,407107959,380567571,992865031,134638827,219980029,384990916,967075379,479654357,690145839,721938626,339881632,84088004,222843502,119257746,762694371,274404454,268268269,9600608,882102287,59017299,913783026,88736863,485278932,87602465,746804569,649958115,389705094,95875155,199468344,242484641,662882928,721188838,623096598,254259814,645214946,482663719,876369092,337973049,218788228,681744332,251731179,96119441,364720921,739169287,818287292,469241256,977837808,975172212,917151758,79462187,372105631,299938731,719110986,853354964,441085282,999763708,116586228,752626510,508051318,216499732,666676284,51613720,35882299,216851642,138776713,45953327,36432547,288978034,393291571,889746909,47665502,895670361,818875504,410880683,511714076,499447675,850981249,993741501,833084588,59292076,89509124,141294168,407146572,29536262,140211555,539022704,61541660,829518922,260685730,478424230,697259242,17818615,977235372,439964948,704684415,258649700,618606372,948959077,941644517,57897407,271627358,838256031,869367275,770035315,247082383,273216361,627342041,740459964,35859161,34992698,859239655,206334088,818410758,189829249,92467079,463519972,102476666,43440568,108670043,494786260,815990636,524049510,869678223,908192479,824715324,923971308,524500677,655485982,161790364,496350646,338822374,253986552,701972875,575932085,981755566,248937861,393464049,641101008,852163035,528665980,942256799,758586393,744073490,845869949,194489703,318327587,749990032,500943581,15848205,658766363,253557587,934809061,345526775,472725937,562812906,324024685,11835650,791747535,92143933,120351022,603009858,811353213,39776088,87770308,981784714,384323228,837166467,736934303,116638272,479846371,976862912,622480669,639759346,777686271,987681055,54383722,785139188,694805548,373751428,250582921,331721480,375366748,629462397,663039835,210841140,52001008,748075705,539104397,287072264,220764817,690020950,563391428,457309351,947268222,440731943,503646076,192041436,119977058,553226429,265379271,53356525,700908385,219422900,404236979,165625523,529358549,51867169,439105857,91306085,716520146,613285093,354031029,669802213,49494895,577507454,334673516,598111919,96071026,905515085,568405884,190430532,608295872,252055915,466011521,175751416,857012665,432018804,90806899,123657054,687419929,797704421,277795526,279956904,99014951,991938679,390804870,45436142,727017418,947276543,226077921,793046704,452440846,726683273,626268822,882737407,350565973,60159421,782074657,374335490,476978367,811938496,139209234,872882833,873960152,653107762,993236117,929030288,5936726,432779629,200112214,326589496,21457540,7105731,752893841,913137563,184879879,660267722,71599605,576697493,754044518,718191657,434577990,360394483,246191241,328178296,954615376,370297695,185750859,620948122,297540612,423135668,115795437,139682633,32343816,875109977,650863714,932227027,691932855,691545480,623384796,803036306,489452125,359496865,985289622,309253515,506379443,34584018,78500767,807431711,555601384,733563732,302026297,652115818,146997416,979376662,68887626,886601605,517127280,491875551,287828354,43467565,414924975,764653016,981096264,905467382,121166632,426065246,961089002,443842458,449485575,449567457,32779653,964792917,418516100,991148775,206811646,254793476,24537592,879427098,548777432,653014337,570525789,105430446,88475725,745804929,674372742,911469575,861271552,144172262,180127127,592164866,868661242,788640566,205902056,792678453,351192161,201587971,152812209,71838498,89783428,895027711,755275189,927242684,26447356,557554519,140627550,733694659,355032739,325673007,443391024,304685278,244452898,176618553,398598695,39750450,804356089,196208536,82444985,111867736,551321336,813240994,200951581,548928783,49286947,230009065,291790855,423733884,432593514,12539634,300231232,547229421,405397224,693015484,352916838,123463252,577673362,182627047,658647366,755563724,481683135,428079333,659132281,315595541,722628075,190032740,365056669,939634982,997886083,417092489,686838815,975361080,150994009,223617087,235998959,32207904,152363484,972568364,458456431,898888959,79277268,973182136,36704200,352661289,916397081,133024083,205286454,390695296,203825924,465887703,449247359,95343508,1495450,950181542,12777302,792728592,400899756,265998453,368025095,644868305,99119373,37949095,800775084,346821039,750584515,755001127,970555013,625299457,770489028,75680764,449260102,955010040,560964602,678855484,90986724,791470760,528332380,630408893,745434000,882619980,524454031,18990307,780983502,569667650,922095224,412433016,477465974,771719826,286866280,260780445,70299235,989193951,357317961,78693515,544958631,101956762,42832275,60981336,2088042,733983542,915322026,391927521,586478676,790146380,98819259,288900391,88345670,914475613,51166112,955385584,430281669,166571434,40394128,299276844,539215834,219531698,292342740,109330491,857517561,534892710,575230628,77269649,29341464,13725216,898955083,190623336,553785406,277192544,883056665,273884238,114932545,876463740,928721985,912234077,825354784,933957293,855226106,470092749,49473708,221417545,568497142,576720091,340870526,317538864,378824453,761051863,379038487,856332585,739332479,620593011,126146045,8692235,61505649,785808536,59635502,566502612,59887664,509622052,846022306,400648733,135000764,653582825,387685370,362628592,140155558,952386194,204636398,202622339,357566009,952668957,16571914,937241644,427759963,733931632,835849234,427540811,991106193,638619619,949647405,625471331,364208052,916336014,254154661,25392122,209127279,518931661,546314538,61344172,219348244,503998656,822886202,246688912,102600205,119760541,61708857,53641745,199633631,665958181,867358481,574994331,253309617,62144565,579630091,650095223,546595603,844741402,347331675,535887757,912094959,841703627,38076200,789545172,584250991,211171653,164482058,638495117,211647360,924260088,290080265,384113743,256814297,628737787,576442869,769546244,262695605,46138650,796651139,548132706,909027759,623859333,981623655,972371909,97099471,656215955,693028340,568987630,230417319,710864892,54711583,207553143,625210251,64182364,469179532,733421118,52596446,372689005,367287314,129884920,925443666,500617819,42754987,323528411,906388051,562464986,918984186,664824878,354309205,50138951,310233342,1484078,320578829,724887258,505415775,225106540,292410344,98067272,889661833,410771748,828327178,351375723,139230858,881812332,835215977,521808647,507694359,866562182,76498920,522127534,572260874,202232983,610615727,587153254,597382013,713442766,431366961,872699833,152784221,601444182,59819023,148951343,252267977,735170261,533155436,87132499,999547086,416282499,105722414,346109538,677289090,179901461,94363698,566214309,863851506,762807622,823308942,116250573,406240219,828846920,851249998,215638650,79372992,434531757,730840099,416061631,541077585,445209697,599329909,32454711,591438595,399642780,614839291,705633051,169989423,651960429,830341787,998654481,446655793,488566686,155804052,816136271,824253308,955824406,8607013,776663142,971821128,784562861,391390825,156163592,209452688,338608361,952037355,138655335,946415506,787014591,2449064,152207933,298684932,121347663,966664547,17251874,834932551,53235159,15615092,449846310,424494730,335230354,12448528,916496337,801219675,22105966,20299631,873481991,206590423,477160740,936619282,705140064,474291502,750955028,539762177,811983911,902499139,419008990,478194995,932452469,185969255,996562400,999293847,809566989,728975309,493812228,625303988,492136476,378227535,111564203,99314568,378129235,606919750,745893578,371317907,945563345,704151615,41298335,49855520,989059466,244512213,380547180,443132072,40424886,609205128,501535978,441867771,473175871,534919056,18027850,991859301,411203893,294432183,512355571,543635905,493220997,71397737,331385664,173758177,568899497,896649635,97664446,561816192,752121663,820043799,73566994,75844642,56074001,276370930,752070627,109765394,724481341,918598275,621269642,613381380,179348060,28782610,565505695,839077890,649965959,876044271,321157443,859718168,806251138,834042374,124415849,201080543,568909470,857244424,32225023,233061095,840630115,175429192,90866260,914315959,308323559,116015902,111597085,297457273,22457095,626757440,297984123,80269035,254919507,995256962,533633851,892423885,942444547,973604804,343529266,260330526,743940121,544799391,366072307,36615094,209561816,25239010,930741189,489257353,26426086,407091051,96394815,904985867,618278615,528293050,323894652,619349597,555439770,164800881,701985984,796255048,687987279,743221283,200707360,739273730,426177146,901330077,304958201,536502465,506074080,551820440,257242265,586166444,191935519,132808617,671895264,867664700,72144701,355212799,849952711,93993933,355551386,98133479,61940657,654537051,38471154,192107531,83352076,531982066,841139379,937673230,238974924,450106356,145615489,375649690,735396228,36015511,515283501,715736603,122158352,707012688,528206943,669672881,230317040,172959386,28521042,464299613,675506140,278631869,451471823,620182888,321154656,19898481,219299813,690018839,734933273,845065414,350550418,153231605,323671060,156406147,991107279,656872021,627606298,886860069,566164434,25602381,802488067,219638909,739732948,908824553,710564807,99128860,404418526,276423727,846451228,374111268,648941438,836789000,835297375,742381186,320604032,355495501,513379353,924975872,228338649,927375132,105017245,379236037,881588141,362205134,258526471,694980216,368934279,893138264,64110518,616168879,577182097,308849358,156163685,211015739,839002754,534638854,396618708,974363646,566989947,808076068,440869826,673562010,963377311,248746175,673786163,435749488,515387124,102823295,12740386,172281380,725197504,424753003,381057371,427977621,890120922,684229630,865440303,548431390,486558806,123608313,306703451,804148157,203484128,956751850,563772792,631464580,161012586,309137682,914079281,979948776,739967967,356800170,759093344,674464359,303792847,70729188,625479434,500395173,595710959,545325599,974620644,236882970,4878899,981234063,866950106,946865225,110012305,786368646,883469684,773043630,268225060,490408367,251186983,894256926,331088507,474407772,912126340,14619025,888817417,458078987,204660014,599536451,208838811,758595857,903134938,574485970,299220878,746078919,984355378,994305205,362818059,177043780,102937943,792145675,341231972,97394492,112645186,733021604,927899236,969193516,571960917,810328047,989680302,88968277,79686736,412659871,142734312,782305241,102277131,423296626,880554318,959589727,15331297,768049617,85710802,727405724,676579475,345325460,384192026,425033031,999542095,686903831,713579923,589081013,577951399,353606190,764962659,535793802,687498343,322629941,838188290,85349357,533524059,987611966,686183477,491492127,79050705,898778598,371923588,742330746,265837530,165380950,506766010,89164646,439598294,984781578,567514017,233207392,151960147,429112924,643805620,63936685,842041295,270811335,8259352,21470587,78903013,125529292,734847868,202642157,690647135,557285910,128104803,71788305,246189677,301892148,544957222,871254277,627128293,88459553,474002125,182363083,517171712,238644175,186175207,163030370,9778665,579738992,539932105,520480160,802133467,347822581,403631733,85179305,822943742,420785114,264740005,692126029,790737251,85148499,305187300,92002064,883442386,314246144,872654235,533902282,901954986,863364107,13543570,140998055,518321253,231626939,359090340,802296310,144262657,113438736,746841063,908807704,427383664,497420211,135132153,714354101,715788777,851563123,390384653,425299964,983896310,514178848,122681386,114731960,652715292,839443768,711331633,102271560,684169898,9008226,515872601,879322068,931021869,911678819,83068166,55273990,69993004,137336828,468126249,565267982,784297724,437221982,848295087,944573354,245242054,555061563,43705351,909405561,738148028,40877877,987195346,126502078,904592994,457713045,289702339,474762402,75436740,849937450,984985953,500455926,616786630,222304919,450206431,34597436,304017093,751685838,85067612,93203138,742540281,640008628,672401551,993917143,637616035,262280293,153935738,627637578,58077960,951676560,162719642,875319041,17118715,537391463,415077937,188001703,589156162,693496995,210242696,731370935,747887695,526703974,386098084,602400201,95244827,342963883,347873033,251578497,677476714,392835804,26626950,635528652,539372564,706209161,115251958,9408512,362554953,842967110,591577089,579827791,32376898,283635504,795703035,793217954,828650880,703889365,928629879,364208535,924453795,250746520,933846226,343028106,72763925,25092332,613007690,134169749,719099249,656091205,743838737,988322150,737344083,561359791,671324644,867188948,20620494,262249000,982499356,864914509,301346220,959479914,524209275,407364931,197507259,287762329,288290459,574636781,686417708,340266672,113004343,888448853,706074780,4194138,771400662,365127873,136360610,33678077,677714487,94119321,315463855,656865120,866126260,132871032,366399100,27036329,719005495,434872796,20231631,523584569,290844355,548293913,323466514,220590241,696384343,138755229,684871739,126969453,524335100,20116990,951318351,791773342,525882182,252120400,402327269,635889327,158786348,547461262,6981617,375919981,983209771,67441179,198486993,721766138,381338041,57252439,962046995,719466702,743927904,339468272,372176003,689702357,503766171,417499523,878386890,38849330,691617778,483992213,936552702,379108582,93957025,735238630,534749572,316993909,957184003,384517322,597315609,390369316,374552427,828071232,699163664,606163042,119825526,715438243,402589126,387447563,660773637,984578422,448038419,897020329,678446141,299104795,942555585,337831754,139010457,472500019,706271305,159706166,619951790,86562933,455259421,60854486,579130230,45887406,75981947,68791842,838286408,586934936,16057259,877369647,328936827,611322589,729964653,734826238,46128169,34539816,690102822,146435554,712053772,354359851,753862626,15637882,832877840,879445734,861992684,379335904,412569163,972710025,337364142,722306514,80524307,457330139,503673560,8470093,61405858,256104846,589896712,255018963,873835376,703481177,510665104,49244447,870216634,367331568,519156829,242767242,117590641,99421556,235814326,224048367,835049556,665233125,566244171,11237071,30375008,997608626,403345053,207410770,586852309,981850339,487282603,49057541,23854786,933903469,157627560,399064169,273037380,559670599,405383533,462910847,602331026,139642024,911354844,80471282,152096120,566927488,758327655,44936287,915889021,183994251,14924877,734304687,663333678,61514569,728705554,47985815,984203658,237325743,856630122,652090966,83814921,721083393,998366130,249812899,67842186,702782123,499082761,12838945,35783915,917816823,372307760,756658609,556062507,41207052,515662139,637054528,414966732,466462915,172395786,500535499,806686394,913960447,130189385,393114558,62173065,265651013,971051956,741990939,997152222,175013966,554613819,108406531,360907370,276348462,374450951,270047747,852516296,23472666,161084992,526065324,182704347,603323397,786035892,378819078,670714238,345513541,43280677,214360584,428259269,181327917,299005926,280864302,317267608,114792155,871434079,354093213,567445054,74146251,635525297,837490148,882073576,723955169,665160059,692728978,980061437,485977747,740662866,151065781,636910513,496495343,268756137,826284918,741355324,51789152,482379207,389543202,167934889,688167265,827783760,955567632,135457336,884737488,399167566,863347112,875392252,100092345,565325392,749187594,692248575,348379157,168069977,604086212,367260646,681675844,100653363,611441752,585253547,674239747,469201188,304414932,995714970,788923366,663954362,548910900,748727366,754152589,387057307,337170564,409303293,770324110,805892654,251452727,711143971,450225042,140371091,718355540,248497346,786684454,541782377,405746959,128560688,143912912,470704040,586023310,933766028,142623967,75220473,948578784,992511007,272503331,528348713,904917624,471318514,530574662,809220468,347447803,340167406,385102906,701807662,301185910,205611969,212153538,634637724,597931197,353643666,247338144,631329263,827201992,122232513,805952968,472171547,628093342,128168920,208940499,527203848,197545814,142777636,924494553,935766226,400213401,260826781,494563318,9466667,192482391,941173155,80155930,146942350,53882400,510881413,537266163,456644484,864771857,844256281,990859038,779652828,472844780,412723560,65671688,730444236,559748200,355118471,619087084,438351073,497574701,229656867,607828588,988348315,384120660,580089738,139952833,131144275,823608103,849282206,355213211,63898617,202232419,601136579,184902696,250774463,403484227,399024541,961514653,155307874,859785791,795307252,790765436,765875216,840753772,106248744,163729751,672351828,951201260,971308552,759632617,148091082,826246879,102033851,983962029,471234434,117442102,311936721,712887520,689282027,236235871,511999172,203110275,322876842,692886103,680399087,910013512,218562250,178699380,11319732,710648297,709366712,290099018,906316836,365554481,70931747,882404900,850066696,9739828,74489180,542639215,567216274,524008085,173448248,9395157,931076046,674748011,776164717,977705319,541408167,558850430,653188679,998703067,470262117,955579459,541255147,927505515,1397032,5080354,72120954,749075548,956575100,888102836,125996580,791601274,574397531,753288830,902245323,448090772,629433553,385280149,740268538,320551095,258761920,357204265,315288490,4472859,599370724,570948769,979025787,466698795,196368721,479706986,781702864,922566549,537036281,887985004,500099225,709658795,111192127,495305599,954586621,34496057,540602465,695297376,404475105,20325558,747710589,490545657,411136366,514010963,448521838,638930296,83249872,961723085,363457204,181735560,500789464,573087433,209308214,57917490,402140917,444333488,905270775,757255008,196827334,745164736,652067226,684816741,350101714,847292996,489320515,295011242,507181949,844421900,626933924,116667064,756732093,791108095,875472666,304126796,447980512,130798802,459694333,229471403,992723856,702372827,855474408,555358591,947909075,474130079,185402314,57919601,644641916,441683097,664327247,373538154,754032675,519146356,859726109,146736947,689620051,267932876,667617751,49485482,626324585,819946148,225325215,820197422,153520039,876414004,92809033,561268487,136778316,25654722,327678185,139184387,455279304,188006645,672216356,821807003,642965564,977501022,609777204,733504144,448014428,493803592,125653667,884756268,921824448,156468078,31981596,82245731,472015896,159550632,153375499,801635293,919451820,727393506,825736618,908990390,995798550,46168779,510050664,459769602,701538908,79204726,546947320,313598080,511039400,45070025,16139940,474010636,325407460,629814958,146081621,412974204,983278102,68396649,431707176,148242397,428935859,22379234,318147613,20134308,680855486,345281986,446503086,862482362,19419462,758362068,475831931,78162889,571167106,146627030,989728679,754556869,946361748,238008954,247434095,96494073,218710004,160012142,674544550,504079337,238429544,80860706,816220838,891065808,739564525,18601417,41865282,841115514,891079244,610878308,59889896,985608785,585480184,188360512,177208084,569427977,188878407,291534761,60024251,657756114,454171820,108897302,373866048,822496192,341263205,829348945,344344516,77335394,134317679,57875112,482872449,89526908,85684787,290171619,772016774,189725444,849805160,554566501,520154327,975330599,431678420,812423952,501312216,769045709,440138448,473215268,990043013,742601113,514928405,42605425,957323524,788984544,899194430,711339649,236996472,410518297,863543515,674348757,153848611,163294089,147136604,609699240,570646843,992501377,465156990,846034428,604383187,63552177,615044858,13113973,801685726,619595604,395112125,630048351,128255547,103353997,549335734,653482885,855477437,606266994,866946790,891133213,724956713,672745960,132926843,511435999,120774830,490521395,3364932,719837302,530151163,133923716,86011334,128974685,659509550,6883261,308807845,458454694,76716622,886077754,657203180,898428317,720180340,646118466,281233761,84314080,875019187,272439831,254082791,964956679,23380387,757635486,149070139,101388702,85382443,296621883,807421472,176493089,437408894,487736355,232816464,24084192,849067886,48104265,827509161,635349533,823886825,884290497,683545839,110383201,932071846,231289435,336132975,504919215,114852139,879585167,703454399,60607258,511915106,730675238,940210098,719421038,769431634,483928982,873829285,955614809,780877528,936046279,812096878,299146792,500915517,751197979,328072340,321296531,49886537,362878538,46030686,543626682,338210036,699840021,443298328,894227253,186879465,55054919,328528932,198282265,428386289,523174479,988396313,983801624,70274893,580077957,587444497,197335820,701354350,917800645,100404114,717281103,163282441,951368668,282946092,946173786,226415267,20369985,908438022,656589231,169722062,660412818,362744430,732539755,271914034,213968622,283004876,579651405,215341043,519943084,365431723,800716619,511683431,131880807,903556701,13584348,117343763,806636795,80350054,823627262,816782450,947165526,862203918,634578448,956184534,973332437,415329460,913360048,422196558,364559196,168540859,928265398,35332378,564263983,296977129,542611475,455495163,520981564,846317329,271154422,125050198,125165951,277648044,741689155,574540897,15357545,2178331,689944274,274697896,905180669,390327113,458225184,514309346,375499047,705528043,198098545,842592965,952794437,978030627,713892429,191896992,485285328,47616390,424750046,331359072,519805011,192322459,193658256,22078318,703103342,248338131,258241596,995031963,47042952,169890746,140979737,210450627,138121380,123694900,761971160,797277637,340266357,107710138,103058592,672409771,132070683,6856761,424948836,377455308,224668318,724169200,321916851,738186542,481161253,246743147,221149272,709105194,189733286,981605654,669829102,501418318,404818376,347230314,979797077,337846521,32694357,531223045,176196736,751571317,160313165,438870817,288472452,485909485,593383432,81284956,356656000,690533223,790250573,702507363,969137313,774840743,200510771,375664632,986526422,975819714,62299637,38441548,280476645,37345928,400765550,950860436,331025456,562193262,647086212,720776676,138340805,516603581,72979624,148356709,995672574,76373794,212113430,167563990,896918713,325091098,400664696,255807258,90323912,950534202,290461559,350071060,332091218,147102373,595905314,664366437,32204484,680840700,889752262,930611951,464637934,712194824,577537168,41098136,394121065,946150685,631135338,69893233,814990700,897994334,75700422,986673530,153296576,622660079,153114500,502970972,730470390,644813409,176482301,256094978,424045236,223035637,200987044,790450355,765276143,716573518,362824650,287818717,28982153,210214758,261816969,956783858,308752670,885633538,633715809,490196390,776435416,84892471,858618489,858320430,936788689,50374797,540656261,806468170,541236973,622055097,929621683,208094256,129761854,650051982,174349185,912036365,649892847,647250887,340985754,106692213,27178646,524970158,103602208,219029295,231368685,313582656,458829654,83702048,764489107,166739926,724755525,438862891,509765239,105082568,329636051,832783544,87591440,123033885,596731712,521252094,98147745,94687897,927081030,457012225,248438834,803273270,531643848,451676747,123878331,549928683,29242140,284848973,508618626,13827053,463045895,79104184,797600151,465791861,778893090,588830096,862778096,901874928,872334370,452898521,183397479,515374686,893777829,868839816,849471559,390185435,224526685,491227016,125318844,345331979,493756859,487695783,550922860,558505803,948988562,289715265,899031106,320858250,333170133,100557602,794965203,484398834,973675839,744435933,494998509,88292285,17233918,887651128,976591165,350196134,641231358,895471838,422761668,124944731,854570798,193749428,554406122,765126699,352351857,365245820,971212192,933088675,495770331,968381335,954020379,900579929,375101225,107279561,308801894,358436237,546205424,729453890,740367085,829346877,664092709,726625282,444592663,173279128,107457542,798139845,153515753,804379202,584668727,435104595,621110130,79946843,489310926,926827497,136345319,190725084,470885464,487732831,173588596,13718924,231678948,440227025,814445260,320718842,137623524,198680049,25996105,415829903,941392383,469753632,792385230,865444141,405915234,454769897,423359206,784852731,175290043,545167595,466531063,317759222,580392643,788426227,105495199,29295749,599898280,54669295,851323796,308477989,564037265,781494997,576429527,752328672,4276768,12679425,295193500,422908508,445400964,873492153,377383157,952488686,927219442,281313993,432773304,886786517,684481039,2925494,924137424,21444995,796261916,448912686,765461691,687595107,594437420,408770674,201509743,985517860,57303709,30763307,288320400,77855168,487246131,583556284,65627917,142268686,398980000,212914066,531929938,965024083,363260837,821857616,346134608,98640580,580809732,1485040,336747163,883137274,274174632,700617209,413573740,322261419,293911399,556494893,718383966,726253128,986756395,191503562,669863328,76654700,431311856,94033745,463145179,245781656,241239211,851272319,797809119,37454812,876273869,885043735,458315023,669728350,162584523,751857655,470807215,172601888,817008166,238785622,415991289,506323238,89946583,51216640,243083189,778239507,341478850,158727166,345767966,24434358,291856907,179364779,309778843,952653973,764735826,18378865,448917465,845782344,869596115,675686970,170358032,404720951,857291986,831599557,663158401,56096255,857415330,964179940,60651318,459452948,467481002,458019888,4361699,292631095,513262035,100695893,764716971,701482880,137542130,978174738,195503781,975045935,149319288,348373720,869668896,544412168,300466287,202831512,725652973,282864476,367432252,418374239,547353173,337813441,831223866,791370705,994191642,601648365,551060479,369479620,468749863,101908823,675595011,979308188,918045108,61610108,979924458,331255341,923881741,19148108,847187753,660963639,675953320,558956610,290272292,316544238,842014447,967060646,25015404,113057372,425202187,695063340,411494278,86987006,347224813,94363192,912215036,505332697,621793172,822415502,132590022,145452746,787911736,48379550,11773215,303928981,418271101,961396454,316220928,496089149,238809589,818804658,574677030,362882651,908136455,883119956,337616075,454555729,911783502,694991700,561945867,138590810,861943831,912768602,71698224,293724801,715309601,387986679,924740239,563022112,692666280,926296151,150452754,864162537,340833276,838961761,845669503,120561075,985886982,611664800,246075411,883412202,599922234,457264173,542466645,961799578,649075055,580501203,465510500,552047479,132624513,725142983,508418556,153239279,659669400,753019986,678751509,136457477,721259521,811065779,149335075,613705829,982890040,988689556,824390853,765554505,100036358,624351883,876998339,530814212,540370024,83628783,887629321,610080916,543024434,599141066,213075479,304336004,462150652,65140612,187563070,659502272,91583337,288348638,552451234,121578788,117741619,843930224,598764911,333489335,22934675,63509912,904697003,58308661,534100973,946387329,667948821,111790256,396598623,636795051,703409156,93186735,466855060,320725860,255575050,482571350,678428378,562054,856506990,730095089,134085512,303327990,54833599,903770986,320105049,352001386,562825595,891793777,882616204,106485730,851786159,843983411,699700242,241516322,420731024,710154444,644608860,33594552,421393459,751776185,456045994,188863593,42555863,917313568,504035563,650203573,220150406,101033508,996561335,981394392,621137384,330983399,648319841,772521387,80821547,158075525,131055914,131503354,416197915,684119126,362704644,418361522,333618554,840213339,760609548,387501223,562637257,666859236,979004337,106188645,153645858,50591712,684357950,81652318,88458193,658166027,108150092,907430882,909456427,238547821,68742245,590666785,312733992,227719335,255982969,688993620,476925294,67424232,913658764,354770498,6134392,607468444,377859048,360854135,174606395,939997541,294459186,173216414,53423344,237978162,84418020,119950051,660846271,850832991,3958011,536254976,641493751,217565117,245249156,881446299,125750287,154143539,618160269,686735475,386009347,903976020,825649262,440798098,822534583,779479320,851663118,716495549,992861892,874860232,748366793,136453119,440993193,599507532,722797178,884663214,150844448,211934076,93623537,572756755,94054009,803722227,280308137,352715619,36542813,787713627,13728881,399026247,990187395,21745740,994389346,776975846,577964893,787421270,395052076,413783386,905319516,783466417,497830762,238306800,958364523,105185561,267660824,390207081,942836076,757076697,347438004,382497035,209111774,51317704,794182190,209201225,407237014,195089887,461180418,790803303,254822238,714961948,194455071,529246141,162625913,654520807,912941893,836716414,969849542,860371664,259161597,425103241,825056496,422619593,239078922,50517095,577753678,177992990,83462659,450088322,197023120,740772744,204806749,563722880,940077243,634010700,796957064,601868309,952691993,256254319,161627198,694481909,583823118,462361083,306887135,389336429,194689794,533773377,882932298,124110294,508068599,506941499,891124622,373546354,891850075,681333043,781647897,998736180,26792308,119733264,164790809,532705880,121379395,707005693,617663400,132814202,972783781,784002656,920465047,576830519,49350275,294362761,345580017,367564231,134556576,192092541,831415146,65751440,716331031,582312935,850519166,24468530,866185711,984580342,480307859,936135718,167814504,605318795,755930304,200342254,690883060,227510091,241207777,322961081,315712398,539160027,429067096,873574424,967133276,98224167,231628804,744940464,177695016,163359513,99234125,26123734,974933350,404586840,957793478,97566834,275756377,160696591,86155589,613006245,316905056,256810210,560047578,298818645,428199829,329803484,144841259,41046540,112904249,792126151,13092104,788638512,171380478,409101697,322562363,56909913,647663454,478043313,737638164,61528217,165108912,229590638,494717785,812614958,416582764,709825328,762628611,316659781,429440579,708252264,93945727,545353144,290085812,684363594,176511026,945897475,24907231,442477408,774905273,492087903,354839702,21762373,480961599,186125663,123322940,366933225,621162038,745343177,503641466,114561166,284169250,821932400,603029296,931026257,985427935,486396459,188020862,118182897,670554982,23403018,345016125,480165975,53480046,629442185,530358173,672678561,151850,404659303,28195472,434895564,48388338,513978200,45357744,556865879,304073305,341935853,249641999,697514602,807665419,188564446,664264597,320579604,92417752,72954592,82148954,431442013,134098797,526608985,937101608,221658558,678740408,949882970,289644992,865436442,276518141,78762257,700305425,468387346,658557967,46013309,44550021,73388722,788637276,357628448,2081230,57967767,454167878,835622686,560410800,108523505,179405741,205248599,754466311,571837089,669613076,18152983,154507407,498260226,220878729,102551218,296436032,831307362,254225752,427239981,230023677,537374739,488502738,228513663,721351783,7208144,326665485,298604663,772266580,93247592,696700081,2912854,711696944,799602596,115651693,871260872,383465389,304368276,211567578,730847661,543156165,20165405,203502765,122500262,572569608,96158027,13235823,702135029,360792138,487127885,743679409,457980101,483145237,379307530,83170992,428965503,313584520,283136480,644036186,998597222,838808849,777666235,443914581,307151767,542039159,426514739,132804687,812865176,681534465,664958735,456560157,447487968,442546382,141172713,513336034,196913439,44847824,783596449,535794939,499586480,681888168,521699184,815433365,895414048,451485138,50989515,927782030,353817343,225865258,513786957,978620290,93961657,813088654,142561917,239367545,813457984,907440286,67509455,198518078,451233155,903857106,620040242,425692050,131234771,783047884,698976150,749582538,887621442,477658563,713595855,856850137,847894355,6426640,76829639,638070826,670523111,280725699,135250634,119707112,518232723,891186876,272365685,362416038,655706352,363560238,765944351,209727139,656339024,259460307,357576339,919263845,863064975,73977918,101319860,514312105,214848138,825623337,5076623,570940528,633497878,767892298,736617663,882815664,518347725,676541843,505823014,627121472,973819006,3160055,216931788,692811957,227205843,215657513,396403433,858225437,694746407,527252288,804655472,932971323,316413845,797982943,663947486,640367390,614168613,170966140,94795294,939123831,642400745,429027746,212218974,941441998,949127868,483547560,905720672,83244368,869217357,397847136,500221641,619620860,819589717,884261761,200579887,389813597,772001429,724800607,196556065,480913947,385238499,40256988,141848511,341076207,833957206,840480920,608371052,722627597,181998994,633357408,554496655,493736252,141353934,411633734,76318929,82975953,859955168,701564266,505396632,696348717,539989047,330020707,855245995,804367172,382480517,724472326,767083170,22505249,81576649,757151535,250735201,743607793,608835058,724220429,35439007,770420430,277259247,649628917,506346671,838290083,294195592,37959350,973130869,175059731,176302527,736622076,956984955,541106302,573351247,555284240,845775465,546959340,161113151,999333637,123812450,797171785,63200509,792506654,965755084,764292762,368758227,874694525,465317960,256489924,826473139,609818377,425498755,30009353,501517404,129694553,80450566,365448799,87712951,810764193,523030114,709537405,11452622,3668302,523609598,711506758,105135210,421411567,263138763,904360568,846296557,715017996,781948738,760003573,940297633,250159558,806194127,23342144,907863963,598314206,348424988,583846525,855762532,102891365,363814298,533942055,422936150,117001480,496337355,908419115,131797860,509466472,585694315,846798004,552903137,274261568,807245492,366280876,394550630,575915052,695481935,211390924,909307530,238024658,511371223,386589667,274501094,537991680,912990468,653116439,932049034,995371798,109177434,787077278,701524404,835435998,924734300,670226761,949443612,495289674,479913724,754359714,927744957,523710010,606152664,738381058,809929440,378238325,499933155,420509021,919412248,416811971,60118661,889999915,797948628,880193859,550827677,751743700,910070599,178023459,388533720,381440091,624923142,888213764,842879829,124645322,117371029,57875035,481578310,813769205,843164339,611437598,722458691,490679499,513135213,116682186,10887547,36849590,294242303,823031127,534959740,347298769,189858037,930812064,532969831,469657980,539267135,874726183,642888897,43463822,144994952,329197497,904457407,326385983,688960421,918949701,85235483,181170232,943761425,277031811,122079359,733882406,8507852,257547862,72862860,540409230,949585447,731626872,754453560,357531032,157789096,612011005,769775552,969191514,331291881,390525874,858339086,457361503,823786886,352099371,62175843,312340859,855762523,895718680,276467868,233823946,131470059,442566006,116488212,459776667,613258941,61978012,720836045,929134166,249825556,487589807,124289297,576109795,466538820,655152543,132032,864556755,731025683,594709694,896933920,580675147,34482239,308363339,577576940,502524718,672730353,77641416,396704983,276903924,327187619,484176213,527051986,585663405,327293634,911465249,788564470,74440231,719953372,333456006,255752750,321691603,99927053,141767817,132335796,167643658,88415142,82091517,466098354,842175069,164645884,37413630,184127995,908255216,731652436,391129130,259844443,371299150,630314446,158063271,132124358,115993908,741943927,207021538,487481026,443490677,979553249,534796619,900691416,101379587,725165216,675067165,490713632,879787122,950228437,446436498,97842915,59355959,956169283,509987458,544950007,749991772,530187761,749026302,128897578,363572201,967006492,321870548,166993443,45153519,271939951,649555641,422280586,629334145,862013540,936884118,861271422,349008774,805603239,682222116,691912279,345724648,650893801,83394167,91921856,889891599,331986685,330678467,818295011,598974489,708383134,938972748,605137480,856052746,685550769,594987006,55727988,903381380,214447948,542080948,921841040,80824753,211958767,508605174,142244358,344604373,795279630,326522482,42636889,131633903,462851311,956214543,477693700,97121992,827704980,631512172,960891330,623557870,416923730,145473596,576811195,724571807,646081759,811782859,463880400,865222768,980266517,637790013,245866314,309581148,570456333,292588523,590733009,632782182,831112930,281374422,93898438,543545499,121251002,489566767,931779890,766835884,954315319,415185568,849472273,609207055,888428136,150862739,164845844,310195478,512587477,146312753,209663856,947246712,872191951,999724613,459516563,743679729,670379763,373464579,517457650,749436847,586476452,752767612,939090407,435148646,6970218,184336988,125833273,755910663,870235967,692261299,562231425,495513175,148349159,75801146,532058151,179437749,743207055,316082433,315887331,538796733,765635779,111503407,77516196,439616090,76857528,545274758,120135957,283379697,436817011,484398431,966902618,723543877,549531425,440472806,650319233,371069448,64680226,246811578,16764020,432526383,238773986,574930106,114342267,338574560,383943948,905058448,483642413,145409974,862021310,67474508,965668918,463584447,186107991,973793283,363812172,498210373,175977936,369167011,302676272,484322339,42529443,473272628,13630308,451319974,215540392,575434433,207652990,155855133,320149569,307270448,389227079,504327991,122590028,933783123,282455985,298880025,105308420,185068390,681088452,758752832,393930116,884354489,611575736,896660410,278759871,100812721,142288011,723775275,143670317,688377169,853651572,776703575,651378559,640787285,81409290,298853891,20579351,718242246,284827313,144579006,928327663,727315164,302021202,211979084,57094415,808126343,138358104,807347874,87015150,613219599,400757018,807463112,876336569,938842635,211306867,644045178,942704344,690540620,914571952,670335685,425624211,991064698,941213154,604935476,962960234,35889046,537269893,873839663,775532786,301280659,650574765,370828478,309664730,975219007,703635323,599408210,407997393,296899280,381686979,272381042,266016068,18585469,419322177,653983032,464492056,407906925,716865829,773706911,471549170,905221338,73850996,554098962,45139520,36658758,943422664,25926625,395563190,414141796,486665445,768406339,431665093,795458485,185054820,453017462,827933797,182272197,137134357,360163446,303614607,429554577,831238072,30130947,190642693,879118505,657222175,424698704,468454078,632639044,572876211,161288776,449074296,127135892,612665235,673495858,58582069,41323357,677421696,261126856,449977971,135332441,347153714,46885946,471553129,971760251,554381700,354666145,606778590,520901105,641526563,414531332,591146056,132412170,451261476,232364506,224982096,348363683,907998459,711304831,6315415,354954711,14256411,236814860,653132707,57981663,687717950,511576074,327531708,824829095,895658280,615830137,178912597,506911979,602003404,75750011,465610784,90037020,423707652,991712290,87873663,216883483,880949822,371395936,109513101,193203028,168017332,73786766,474585352,601746106,46309819,733026297,652269418,935574038,110571910,601715293,321414306,881847315,68670189,941148084,658787633,611042477,524110985,902888548,521355112,475066202,886436046,236565883,763543562,307350640,944035445,794540079,781790707,251460203,836793103,111277918,937194936,435717185,179492025,655423787,56941224,819402362,30353570,637300160,602841531,922743549,571413056,985341386,386272485,31569092,946247013,457141456,272940604,287661436,740065455,54818761,68431564,225545003,219207044,71312481,838950297,652994055,229646215,428800424,686585414,11417767,565343964,61327198,520023382,567516562,275981207,644447107,462495528,64515534,980821850,381337156,835356822,387001846,759542606,782759852,152989620,551596459,787760892,660628089,685836833,314918782,85757797,369767042,4484123,788684772,948872298,276128442,971542105,389990594,244801292,589625570,347407732,666694109,705703564,596345,78330758,97574095,397792004,366596695,53048200,168362473,77615543,961857472,829120935,807147740,77868081,911296344,304283204,929246121,338474663,852458716,410230675,117426433,634544994,186901734,281846355,790246850,285429833,888219480,938948641,992949709,203316904,293701729,120517075,39357560,643504800,450505886,418065258,3781869,723320029,82285383,576920569,208315556,554183660,321175159,9987333,353381265,486636900,81629102,284224037,742737509,659852330,532557202,124536965,882172086,439150514,48877706,587325097,338063667,387299885,326233138,474599575,840792067,749872809,678260267,470087771,965808462,661416808,849913762,232356668,93248830,363002078,122367466,926624392,224748300,68426674,581832282,362118783,954708861,941500090,925480112,113165741,99076323,875934236,826304267,66553967,319500438,927722544,147014719,270188183,65340501,252130199,567019062,504433295,537929287,71372739,265749347,476267847,962152160,339491210,112200038,841353756,245740175,544068044,166246582,230078927,465961489,334863592,645235604,475357656,696957552,389765726,760412110,364128051,364737785,229623957,54710218,184611588,446068179,202472776,345849384,245343037,311820619,909044853,118179613,615360794,87620806,616588247,35565485,748652529,496367130,615868962,831444372,409469175,410819237,271969732,943063486,284189273,365480383,825566661,407028160,186869425,886312639,102926659,602495487,756254404,559545082,236281539,279541248,348514078,288203577,54873232,422399170,829396855,149567886,24571590,96326415,902870714,221619074,808111398,34661136,20117924,967016089,483167327,957595582,66496056,700695330,579069740,29231976,675549116,929501,382716356,393251105,209634847,459692449,197807015,237815549,498864976,647493744,127716059,980618838,116798119,225932675,499380829,727500527,476954918,417831153,216662781,466578602,116747195,956010163,190162687,608613673,505391450,816276265,29648819,884473407,462746915,349114618,437039700,725143738,314086419,128618385,113626391,44264863,930210579,368251093,148249397,546584859,664166994,827649630,55749791,476845823,731755135,117191223,976337818,180138977,436822747,580803383,42261044,50236507,156878456,339270054,542714793,44477142,995995016,53205547,872431277,81614470,38304013,323430969,623185426,599708363,157701570,288445170,820359489,729896461,736206941,422261951,670640769,110720058,151176504,143326905,211618979,447260621,916492647,739201845,365489598,773421744,973714695,397488725,564353836,807136500,681935979,177775014,714907321,276339082,571306360,339585361,192607179,891001424,657462637,171176244,124024506,420734752,418305871,752797266,82980116,929922709,972470944,614097069,323031201,346735591,461943626,526116855,48785864,191220250,996184416,881946278,731941330,744581872,593290213,455015448,48346147,597852641,826331552,377649315,337860320,264614150,724364691,312566794,565106196,567149138,188631911,650665205,743369911,905719578,857836088,238903636,606474009,844259179,832544302,361618440,342400070,609286177,863726521,455163305,592916521,823846367,558817960,900443967,237471538,952501618,144567566,381550514,333318856,452661416,138835969,248890341,594795409,190062278,68523257,412124185,729394298,886287988,688617302,594599609,987197550,163544706,709784160,70718035,999557454,945042544,333962374,176345138,305301506,863978659,752384446,734648964,7146276,995860147,726924489,385418840,923764528,551137933,671248998,743290273,360222290,292605715,879678953,486737123,618593416,524186163,811900125,287286415,672517027,580217206,780318793,135321722,166999481,146634185,755477695,390298801,129869047,304161086,24292542,55839042,829403733,472187854,109186513,939668031,198835557,137630345,106299174,656801692,800091864,748844381,218834978,467471582,92676526,127201916,136373447,456450958,552642600,190383503,817879469,57411036,687124549,482725124,760919280,505221075,100267287,565113361,333066224,501642686,880804058,69024035,238765443,76842836,859872805,464772972,834294843,865673616,967734265,816133124,564340257,224409178,663770514,960966280,528737451,203007671,745895061,41737619,404493611,183872253,111988138,988960594,84759225,205110123,574583826,943886670,234540879,89039686,279857799,373819441,39172343,239572819,761509386,833198029,611389894,68181210,751286128,809592583,159133667,735379332,545023017,977070842,615171463,200501983,227964716,85134142,418394270,884014190,127599962,822355137,118035467,694687688,540362055,156715222,97784932,439340747,744135021,525516397,901327915,61600045,17817039,743726118,95534617,480023610,453730069,126839186,482421278,96630499,9633070,841733965,547966966,63897804,774525484,196920052,363013937,174198032,726112963,778486887,204227216,767951406,582562172,744478131,204220295,444608737,88929777,141627374,357867451,724037357,46493775,322786073,314815167,491784139,898950517,906861152,716917483,494372042,296679651,985349670,170996604,606803742,150652191,128154324,111109174,687071684,594223069,308162133,343391345,89775926,123446666,884869616,472359215,487262124,59372057,79244722,426181514,974743053,501232455,428502582,330227283,825180111,145711829,640331001,795557268,490795632,110477475,14546248,813138025,617835245,873529470,211591398,776685332,344768458,405572578,138201446,114859093,434934554,703693268,780311247,8496100,60031998,433454874,811536694,828573961,558595379,307008747,640290735,118806606,415813910,672598032,1206016,942158089,454072492,232470184,853628595,745034205,605716356,202308512,525526561,717649194,261842006,377580717,977912312,79877293,113362654,261109467,950699626,923259080,291502916,879310405,735001828,642764230,888647778,547418539,643441225,736505930,152402780,278511167,570316956,890541509,163100751,45188485,66634935,94372458,67948698,138424238,564356943,504850780,319170163,26262982,606264348,822475468,785933515,12673908,409490703,772640333,725441900,237349281,45211866,252577980,295918319,74544628,327070104,656585255,102897430,672770175,746929770,606727675,812656347,112207687,176931921,222923730,467649742,792044352,785779958,372303634,687312927,146805454,693533553,824673002,212665454,648475348,238643889,181368405,979487742,788325539,206210561,889776116,184042482,825543294,14298991,952456920,393328280,506715072,233049680,3283279,933452487,167907674,23743338,415302002,658894864,620295316,63248405,11537570,638410760,941342908,638227307,5531984,634258267,17353408,186909420,411024957,789043547,536352782,137835546,614650156,821808400,311939874,765879991,128028619,145868886,777999284,953523252,135301028,405152579,521729194,526832857,404751018,569649477,409640191,783096433,721960615,502429333,217078305,653334460,508382109,688158197,320872815,577964088,773891635,635743213,998015644,447140569,46262330,934878674,515512466,61962642,462512455,349007623,993279804,663277697,913620480,711331310,303864321,331530481,460213849,371042227,961681948,819551292,31431364,778936164,519796236,251862456,362029755,812920334,461091324,440884092,913330672,928474126,248456580,894508870,270544021,810480248,252755215,334244739,981591468,431405000,512021306,368094991,465105308,184436476,4949511,227547722,873671994,105003550,710590663,533690652,492573223,128699776,541102703,867367923,526664603,517368265,247143152,501582366,221510887,137296136,577194383,722361582,6052183,580286850,950825501,891356558,976727412,492615816,844560327,805992866,788232164,138845652,850106031,523359526,10535370,974304536,573528177,381463103,804664404,83091447,92052688,941301376,87682630,94137724,63236585,605857408,425485829,812762071,96132377,227631204,129270321,185812861,515532089,598787825,511583511,452525367,354249142,833638688,575094766,586815593,364764527,324571682,467795994,309639491,758048556,649086688,776017034,850102207,459089558,9457635,40681567,835296823,733103722,160572815,153336004,137842828,737038730,517237792,994745666,530216567,440190166,987934625,21167418,864466080,354534605,188964388,943638850,364397433,597273765,41602277,70262842,377536800,239799293,627395679,287448761,106098955,793709675,857576208,166067770,519752937,317114741,840523780,328719072,98997951,706219679,85006562,421640857,614827077,854857422,716071702,311716304,96284873,643147829,100366652,880635847,182363983,325276590,223261446,701191613,684668602,800791766,420173991,731013979,190979144,91399521,700941842,781734699,103112325,782521724,652761040,608330404,832435239,30585315,237271081,85409535,397452058,302596636,293363734,734802404,793033778,28172142,481261763,143036139,767165758,56056696,192547217,30703737,80105988,16577294,27663304,873661154,70299317,990572125,45451909,992013387,853443648,577092201,945450933,755305356,434259453,94688996,152573345,204734897,710611385,88986728,744297762,113220737,23394095,988025842,406767890,900457407,463357618,668760282,717629754,935113926,174425536,47783975,739362425,123895433,44383419,775297624,643880219,317722078,103597082,132876613,667220389,960956936,371692843,11683178,938160769,843108309,24246457,281288447,3421682,319129483,342554222,698130125,769847314,27811801,74482939,999273219,108367124,260120412,714542839,385919627,543535627,600827229,635129609,629612873,44606320,812584593,53721856,398575561,857958734,507236380,404738648,361746887,146703730,131341932,643640586,792198963,89359741,778097734,460688755,910336428,143822746,748262656,386222560,546984686,587103373,906515693,205755364,681731078,28971201,233165916,809378084,849016268,180560539,286585762,988565360,530007259,69834257,178286137,508395572,559925769,399058429,383586622,194447660,759194533,227664235,684422338,956800012,373231526,895503173,156430435,399315695,205467568,932689578,230597993,245464094,198941971,133151865,791392037,205234919,524546551,633511722,207589828,448796468,752647990,869065678,143545477,383169867,779980963,692842431,739382361,104454716,76272213,652325210,725786535,587178785,26481530,338938359,55862800,435725861,325309557,131842884,266184840,353147757,502530169,118850379,944485299,558280247,660057586,834811147,953260356,11775250,924088382,344679748,62107255,745539499,508258026,750178863,172637482,60731455,451810438,868834252,755957411,655929603,968256148,642981048,444762032,872380264,17217557,51145310,398744948,202857327,366547100,219505035,991701346,696916433,491657271,559658619,204035673,843655499,276429130,937259449,727008598,799038803,22895908,997910099,820729401,711577926,153772139,25512832,90416602,360891385,800667145,473152491,934949974,566367919,298091129,731235230,969082476,646173862,212274333,517355642,827966969,94299070,627495160,811942281,202823729,594844092,801256037,633242100,118503815,414751445,143101600,512863716,494094332,71658622,214091143,987710254,190626246,602693776,941413980,478229342,716743920,872265995,96698474,713615386,830602585,293940595,840170643,835996454,399878635,283886982,372821418,799774027,494903794,436879505,180230020,966982448,710741618,130329112,801044022,571894711,845087452,720943084,787676414,388289990,580037275,258207192,416803935,132079031,501666666,283835918,662072417,131315990,611970,340940133,694445135,113246147,95954896,101201822,677931086,232509998,522782493,842738552,45170077,550230257,655345417,94281703,335607991,64426293,66905519,785583961,580170771,354390817,67286766,750751349,411496518,917613264,39037519,559543007,408428436,98988040,185140433,98936575,113146756,134500497,42551366,48753911,215712670,323427132,351675545,528866849,23294788,466456740,68612561,120077935,101182521,560560601,331261618,236400702,134830142,287927587,711276596,177264701,728011318,471884667,101468476,71638992,91191155,493901774,775798541,118352581,581971745,558589777,212855933,909393676,331375411,794414584,613058467,840095141,921539409,453763477,481306020,532358469,931915081,98528796,56561113,80349148,808400120,444760849,852497583,708963275,306489369,146534208,784174394,304876897,963004715,783481213,392002065,46361106,240501837,343129383,774926464,493739971,410880589,510134218,864061680,793213324,750834470,661027518,956589095,330338223,542265044,720975218,327752552,34565487,914533897,823723878,293123915,206153187,925491298,508190265,611319736,889035704,979344949,181382166,210768869,984825958,106387255,782673990,64412055,34628875,832412366,646158804,959194527,22677260,32103301,334763088,749043454,624192664,348488253,854162802,133516666,480151503,455744073,763949709,691012328,252633720,439761921,587376920,854547759,13554377,175147657,654074809,859504448,716247814,124147041,771170359,996414068,653761570,244368938,912986480,586090123,702187050,235109085,901459693,335930666,252195499,664516162,253665265,597069560,904496136,622799217,551144641,991011776,51753100,83474665,651873164,718184001,305903598,245920668,430130248,562100912,242443409,762875282,960470562,787139613,956210171,404213496,918430389,740071865,162551631,406063233,1726865,106132644,5415629,826163429,846973348,204942451,51487816,505770927,544673841,403437104,961533349,676552968,47305958,88243872,789513783,56696068,555559255,818480207,564080014,145472371,117749111,969848268,631938124,322910584,467009319,120378295,854365747,42424565,651050307,566306862,64884708,388573258,252976679,908906540,734015247,93682892,422852593,860142628,704720839,663806446,210370335,729115961,503245323,46520353,769482519,339153177,518825279,905835911,665561172,637279159,249877724,9872314,567740579,746067632,1676191,254454726,980638705,805207857,479487783,392525337,896553953,637020719,994222516,120547683,760807638,569316206,103321788,362504140,988953019,957446200,496295007,196676279,353866998,853395421,766541012,500390331,514331465,747253080,598147904,700870921,589765452,550920859,170369927,811661638,781024122,252367990,61583683,742820905,268510324,782851699,549178502,158368308,963913923,32154540,841431892,765993349,33236525,846484611,580674280,226931992,908011050,922921768,271772495,130089943,869276511,392048414,470843680,785469143,797908292,556771776,869967831,126161772,834542415,938670348,817667974,797781865,579396834,24712118,310696864,349447391,587504570,59499084,421208933,945414997,151329004,558910758,312616306,42749311,228131879,747159036,958012621,278714519,693086726,757302554,995932956,950625352,674935962,640089880,245025337,60182591,24009200,943182411,135478101,647777687,604978766,336030195,924979402,287667359,632591894,573404739,454324284,169371034,203136163,403471389,537761344,189216963,893699581,701209327,627882731,90418559,393782684,553948512,871031439,29373674,909583755,231065870,873643314,977483859,321318663,628880483,472745825,897070522,374556245,892240358,5389905,393820161,390845873,941594985,372896730,711037742,457812817,26108118,712475238,202509394,961288110,642766967,934648537,588062132,840509030,287837244,547386864,904058078,57314421,3778469,666176229,591628992,452161512,326884029,676706377,330683727,113721253,52653341,181439623,28965021,483803725,709097111,53882305,509284748,471921272,923710133,636921168,675573928,417944785,771970736,563448425,267774283,504133916,948717375,819821228,480299844,8449035,269010543,807119266,746789210,37314333,76769807,779958049,307726833,617238833,232546152,130422771,20665766,230156926,629407035,87075770,484576292,15750220,366437537,525563341,542832076,868168876,310401214,468403713,579133067,93568865,446863029,469593422,247219407,428695082,270607489,877186924,198373591,963302371,136713242,724934582,300790243,998087641,864215570,439180329,195473342,463457662,409737565,626682673,41375154,754995297,518065134,222002200,804859139,61035298,116048798,516996510,441507808,865728671,100065072,106948081,825563406,352321375,852934846,822612997,156921193,264572235,374404355,279887353,870533519,43745400,582509104,645542833,551009587,868642845,686463609,111724779,650631753,974120725,779183994,183086330,580860737,65747497,211587521,711524593,404888055,370841620,737563746,958268538,639449313,9412581,869416145,798414827,480170933,782304083,289836047,574509111,481130243,873041724,249473895,19674321,746809987,741018441,832247512,815919851,127344593,386862139,204465635,480092245,814299936,25742021,1933900,83781173,153880757,703571911,888147795,88643915,70585543,713226635,739315469,334705941,143078894,338265396,837296963,137201997,142483857,74896772,157608440,870692907,575095869,605353714,549835359,253724250,233925386,688888492,857522645,413318076,320283865,416899673,386642528,15452274,8331478,26670847,18800462,92247303,710206965,734350729,644182994,318515631,408456824,576105156,388571147,217497102,456626120,556128109,789274797,128004238,381592350,36456508,484669139,221724680,435547793,272982906,998631150,409036745,378397746,824816833,482549424,102896674,98537592,411416907,934096256,43293600,224536023,441149360,76722654,425931087,60783758,183383312,484291339,521512443,178866094,518314636,120415020,678624244,144998269,384946316,571988248,62658742,276963273,324666262,702896985,282084748,501950707,762745711,930254412,897930902,950061023,927676694,523897416,253896590,982960119,19023662,903107478,905944328,547263466,184612961,823649259,186486029,885027008,970162912,477708891,559458551,929438669,72640183,885822763,312031668,161178102,943481447,73430281,487119389,600887137,287498296,145655122,41761521,244688034,833582011,977029496,67752888,142412862,674662385,337048535,860350606,698218369,898459153,90957345,859224398,97393336,93216294,609148104,897638679,540657778,831964389,559460306,165956376,440532557,654554290,328207027,437497293,825974701,822505499,497685954,159023813,243568223,340271357,984723716,742511030,148387071,505966708,540197814,691284029,317123711,636777501,408446306,44824061,738716777,802886310,115953000,54403171,319039953,985307159,603997874,30047527,143107822,824458292,106023200,313473968,779594085,840056248,267864758,670242172,1434867,79446708,111950078,142264752,687366331,44366482,76594621,421564103,679327668,437048624,875129406,977406917,175638116,100263212,935098345,912555669,142405656,553551143,634901597,92382483,627672156,639230406,477726279,851698667,166483945,71955221,904063242,937084347,724531509,968793273,287527757,640806149,398456538,5022820,459652085,666892914,545030483,102551904,746439143,950694274,833308016,312457756,879988177,241413950,847648467,21270671,13882095,33631720,460118879,129386506,345555578,749796536,189318534,98814662,773165103,162338124,112618378,636964617,51316202,123443145,825692169,161936047,590339758,258842144,351023964,522184639,739046031,894207347,852319323,214936171,157710321,435523227,7585791,231327673,978799041,950746067,910814389,586978685,603863055,118649663,280061625,504555729,802698947,261910353,378805099,435769185,846434603,887673471,352109966,240246008,545400096,79208076,603250770,565393903,107673393,923958886,522745545,428774938,612747281,52442980,379343099,888000597,407665707,164703619,860282128,901813692,636119496,86774506,70704607,566851636,630966738,176695258,540295983,193726765,173509081,677310319,891202333,532151484,748085480,348887753,126108361,729842316,33213348,18475263,714573582,109638650,948800002,415554639,402976207,450666989,185261154,980410775,914850572,58134731,551321688,464651989,155438631,909935043,840195992,114553450,154486438,938812821,64728038,50387862,198713225,436101490,196055219,860151235,849378688,976786185,125908558,873742011,488800691,148263862,582676692,314710702,883524531,694857159,241177505,961663224,504857024,217091649,877607068,24304280,253119608,809125527,106279485,325888669,127560033,505773503,587968673,62722195,904944335,713228869,776862307,24219989,190945840,679142840,271106653,322196615,352234218,181065725,187312276,93879877,24569350,413183804,211058008,756439259,164414351,293522146,456770663,837978663,502610593,116031478,811856426,552837322,522613932,157217472,742144672,433459106,675642496,422883514,379831875,158419172,818785171,40137599,75739813,294212998,330501992,147246980,317305025,743659674,333315378,394206670,237430273,258960763,197169850,266401629,56258255,78160614,532931181,613046008,985201797,980662387,848726162,954221360,190521724,200497591,361169794,391941336,818667381,207924716,427786721,829148269,473571700,745166118,29799569,63623588,460744466,699187558,214770922,882359094,80205254,537457309,521751659,697380690,704490082,287462263,333027069,843564601,103211513,656595862,281169279,148048753,114823376,396165426,945987660,38657810,181751276,764928276,105402368,409547357,370319042,337508466,793454913,516253499,838623813,815249830,958224950,906865797,2007420,171948166,567320747,925380727,797307115,42724525,811553577,112326542,27044259,59306427,330706381,494467031,893159774,218607666,587501023,147368302,208880232,661780026,512067747,1145231,68028241,327819792,371689589,749971778,194148603,820889406,46276892,972600786,648867916,601104746,4390534,570239518,589041043,113197031,979472422,176337230,172391750,432702447,50397987,723389169,889816294,859314128,665023221,540376359,190101128,366970138,94075182,573619682,771903991,441665210,363700438,767780682,653666129,787775698,702451109,23676335,643687650,583203611,580703747,367678792,267004725,100569423,200662172,979799014,577423102,271474521,417008219,63491503,949802009,869395690,247606220,487410232,401139566,794496407,840773981,445901407,694503066,732387395,651661739,312247673,644090490,556779481,206487188,889573742,284731380,886738144,18959675,266151478,146937692,561552550,616057863,65841254,432856351,135073799,295124914,624688675,887989120,569276837,589130652,264750425,74276391,675304630,393842015,758146051,140201506,370129161,293662146,662267016,313995511,955232698,8210314,551793990,167202184,51474790,286842945,661567678,445123627,152751419,50140968,698638130,363447692,21867376,98263373,890564046,896385179,740898326,960958354,395525169,129627918,900978346,628844803,20555712,320941573,379074725,672406073,862896975,545369212,353119266,23681932,737756429,49208072,844819165,506810769,48450581,205591232,863626779,133304580,624632239,293974337,259788790,435939179,763061536,795874246,730299006,59329815,162262006,980786799,792234999,695016793,983683918,446495220,730278500,714685473,635685618,30016479,621284086,856141688,32915316,97397311,12540472,314315498,38286913,829009847,294596793,338493616,171001787,486893001,90951315,196351697,193584618,138949521,9875158,408518265,254238974,294957066,951150986,126353434,908322002,499619669,446717113,371688279,82459677,211312533,739273640,424664516,248361431,295339627,938402772,615485436,34995253,902181540,376089891,898424916,870041155,565539662,262477612,529813946,115789960,254652116,796183719,489160776,757761516,119772702,620603853,953862470,601108435,66391557,91864284,508236151,28020669,644465190,766416509,348330635,145539301,888136552,899682814,329674949,132037161,590936154,545051481,662486712,504437467,962553160,429625847,674567893,689383716,590817825,703779625,84229699,456827720,649452015,828122051,198773528,95108942,768154826,853958465,639686932,708107820,606737644,187226752,449456587,109849788,995407652,918797034,814328508,298930203,948650066,836042512,173975441,72971898,811484405,742731316,910271648,55065286,709788523,144046976,783455463,313726884,528364581,171611100,990198357,413005496,509202746,241197305,146958177,319886789,185694282,463037061,576126077,94695463,847221370,78480911,473711919,954343204,90870185,394326278,307219704,890877740,726189296,913931971,651593253,101665696,884326816,146475625,799569913,566348512,764896258,567275842,170662392,432153599,208822817,489784699,299595720,249092403,50389218,576008586,913002804,67469013,873314453,892767973,76059200,367183013,169876591,110098074,80404582,592595711,874443638,189122376,303975872,58884491,829162617,507697114,705844045,214176865,280956261,508317452,601467998,667115957,205768312,899348114,353844412,473792519,954482335,281761255,359971150,573684451,860476574,667878898,936594395,286864255,226746270,288570112,772776036,858718574,392965378,849872099,679610274,537335303,825701886,532271088,610786261,305834545,25809122,568173916,232206581,718220268,122464489,971332797,19634685,435152804,76853724,42867421,858701580,900325798,398888802,473127858,875448212,40612065,253133865,48742926,824066353,754133946,73724406,781005901,946127643,598373513,990692668,130955885,597799598,289342920,876458210,835779275,44718476,757128260,214057345,419667268,804455106,712903608,959673043,622644731,895160664,842332613,665004245,14425305,366406180,146029889,336493058,907361833,541928462,506492485,786997265,711250982,101275272,119426658,892588217,556888824,689709920,630877512,31578945,111846384,546963341,228357958,458922917,503689642,924255198,207894035,912131154,450032992,60070388,78675604,243928454,159244255,653569623,165799356,303486133,210754284,739695863,78515536,848632872,179274908,153822015,863778764,333211406,439727844,14644781,114677087,523443359,419516601,419678484,992962418,416917067,678983486,94832691,6128719,512122333,918572133,181901048,341684055,105618885,108086351,422093051,772400694,992796521,130674904,963297803,266960288,708221833,729975557,918089766,664693467,293168175,950031007,630219204,704814624,299588716,485881244,118736945,599526552,249487740,252367236,48911205,357364212,856034072,17191782,179471376,101354622,98557039,176736145,434505214,284731898,688422748,472214178,551613981,82253146,242134732,76929659,171623319,402584512,664405134,535101316,933788023,157788863,608094974,377551945,848846377,620169796,101117412,820778707,540263868,446948538,759259538,527224692,547870922,804191365,575175915,157708258,400850386,229215441,631232747,559562649,738551530,380085050,473069172,682091188,431867608,697139374,150680786,608750489,657374315,834232037,810093174,189653438,639600318,606891391,269263865,769734826,491731054,6750922,439091341,54357095,692124268,406635055,22404631,537973570,608615698,332404203,905452552,664897400,218681390,33601713,748769808,319991636,800374164,51009540,471363627,141305206,947167307,537632116,519270683,801806351,499456332,996479448,398098161,424231522,206460792,445936170,131281160,976750651,883193689,429362959,758197993,13190700,91236415,693060103,102828371,305074140,337605591,278351141,821222199,197077902,661493818,996737185,789421695,449435277,751692618,844514003,27425398,22658659,719476294,905140648,717694166,17686410,341223093,155186561,968361847,271980494,330961842,286011342,717201586,974323869,898457908,424537699,57410337,113849965,68432278,237545201,43072012,2295223,714085893,502984215,953045491,548022842,62543511,49285994,213991994,675818080,226440155,231641179,598422020,12971239,904744104,495430099,899574474,863309638,245566734,569507382,375954595,771988691,865218110,901979511,275555782,84263720,467092176,365472247,481803487,303351750,306684272,481806704,711924938,336530460,742998669,754201156,410344298,879604547,29174059,495116675,719803178,956629095,2618223,493274530,178148290,339084690,367764270,556149824,361260224,557293277,44900550,315257262,686645285,17669664,59773071,731141148,180824880,227376233,931918596,950583979,127063598,397619977,977327622,635905629,787279131,946584128,473560898,356595482,466385775,230408875,568946584,688040844,496004591,965126930,737305297,702462067,207847441,483530865,418106385,340498289,503802546,28854148,206318370,199733263,400010980,360725750,164323347,911501565,605948904,608754032,509900094,76623259,464409460,19715953,653540433,822686673,40688656,954441646,745384879,57043333,949591169,827796526,22642147,441959110,8310444,673152409,521664245,228213592,180047202,248865391,529965828,166482018,39568132,887621110,826583708,113646491,736590632,428505647,381740738,28424908,996059122,130635089,648632167,726817175,522254667,561501558,906518966,260764675,805252845,235601099,580804403,266425606,104734625,131230413,123845822,565076411,66552643,504269392,285200282,970618048,891750124,355961655,905578690,637415119,32968728,54630570,200472721,736158282,958955207,295393314,840720181,334663385,427840202,935024858,824943307,460714295,192103561,16628286,91707270,223806922,279072157,54436229,874645759,645707798,176092695,150437877,614124798,582051082,537501667,119792918,167395587,7031717,863445612,383398105,113988313,832120623,830780075,775026309,378856308,941933779,979061616,861855376,219083995,3227938,564862791,771208597,284575065,407035586,311678207,455988594,224141793,464798113,463861052,540040932,995030480,815096749,325854808,351436784,810978016,821785981,289648810,575100499,37675193,285250042,806934368,579670749,185950582,682725289,558806302,911529383,73486030,862566341,283370868,642933077,431492013,33986572,129149149,89737282,473956958,570724961,157946956,324701800,507205573,241470468,443041424,871409019,80393440,991289273,213656463,124494435,521875445,630368345,856922342,61443790,332101479,112537578,278959017,507397318,169161389,974599942,36428103,800244882,818629191,920570455,200939128,339631212,963224936,189768266,215009445,241742792,79528667,341951344,509999236,949924275,983858127,79458589,873160536,98863532,594523193,702873838,40536766,135067219,770492010,125799238,976862996,416871035,52807309,60169661,954178337,260412741,185265401,51790104,143874402,30487892,308892858,887268185,982919105,477185011,137520557,54070836,382957971,366128538,981689511,138751476,976300137,546834410,563403357,657800054,192671400,615858702,13509621,8890721,42954782,972472838,645929527,607724704,596874996,781942635,657430452,423221527,411344003,501777306,995878751,246623339,355019863,109266075,129382918,78230640,848025,367854293,714661316,436700341,671009388,11132297,855395546,22903535,540139932,718461255,25249351,750037307,148010859,832443987,30129304,724555283,13857822,980180478,546237609,122903538,907978399,167134989,922128425,970442223,877121574,454541210,667762669,130617239,348627217,835225681,330398706,765824247,131601436,503135598,202372278,804263145,781582375,690486504,5044340,28360147,700599573,324186910,443383931,185473227,249754392,84515037,957536192,68328326,637907584,867377042,679927636,576271143,30831009,426187914,875286431,469042445,576883556,940743134,88222502,430348193,137156655,941947354,59732994,57567009,954057691,380199066,241852437,420343466,638918079,670897331,127790298,287891486,311548511,630692991,77818145,72021992,440326283,128169397,9936016,283875024,526348381,645076052,88734486,445328693,658833456,588211060,196058279,704559233,95178051,575164720,969553893,186366215,225818179,515508782,45654,205780287,100611939,708207162,128894991,674597561,40530145,437830916,345230590,582690514,754038478,823698799,226126231,250487805,880590515,774974128,294828819,736165882,879666985,78569525,401520926,761562986,379548160,832472108,295737529,976469323,242859865,172316686,318585446,581837529,95800043,646071098,632603432,767323905,773571100,543478762,999602243,550327620,144241711,908882961,337722994,104059715,672919925,909272951,449833983,10293419,641274882,834001128,224172905,780676075,490687933,654885451,806084082,528320898,437430919,64931952,182603166,50257977,517724746,589046956,212576822,513342393,96767730,168590840,975317487,418326458,98802975,15215203,171362828,319479569,783998683,853690836,436613623,6518540,828414361,23681826,528953465,331566253,61433853,165090320,917114894,459888939,352730798,84634844,262122303,586524,60752858,457025590,827569458,501277565,393687774,313301211,23550833,681859183,34548289,625487111,422401090,507161226,496130439,932770619,238149011,453888447,641214585,820589449,506888309,204181714,3199292,83409469,703607639,134123222,498646451,62689941,801324866,997072525,983030134,195765767,83277343,275944535,382605872,683830164,594066182,818845971,269024621,836706790,601077552,340319554,794770695,155765103,954499006,561950752,73209358,69033822,48750483,158098274,513398357,889871031,986300309,323022170,194951574,638542543,801714720,899876340,287299137,93357103,35262742,102901869,185849957,139004561,580427369,372066109,635692477,352317114,781320219,933902975,942303480,750175382,114132315,311900012,888897935,811345013,547453619,233030785,331209945,367932591,237637224,442218926,80070662,861326721,130935420,608349412,151902695,463517160,409720451,132026253,53100329,251515998,774539668,435310540,934944098,260588565,785834300,285629628,744185329,371042953,619378761,45599118,525692825,571586017,951834688,879914713,154188149,220436892,473552769,426992801,725141780,281178313,92861769,93097370,112381152,590369460,965065080,52297416,80332598,530244270,551289418,276795168,439787752,667013468,630719336,520598560,851620042,199538639,423932706,479227574,314159968,217272781,981430367,78285562,485448570,436719615,640442437,727999895,279898306,54620590,471212370,894096101,923070026,409039632,426919555,287074836,263992421,219405045,311169416,701694267,542839792,790830266,500967957,278051990,295380058,617926589,54243009,922164513,222468170,46482341,337636257,776025,950728871,621801217,750606395,915716865,231030584,280591512,27453372,847322746,782307343,137605445,480783452,339492681,136923135,750617517,309665741,992210884,670787011,421125705,901107070,644825424,23913337,332012970,979471884,521800133,364599561,53976836,743562196,635464857,614653646,880464830,455564911,900257622,607559839,766451166,137832256,204850057,498621858,856376812,689677090,433608771,43578504,717950257,672335484,31012721,978232782,23565642,930754046,912366374,108408238,744101988,117814413,712873913,253567756,898698022,958144981,355805392,426750096,586461070,848747407,104264653,615324175,265143851,244136232,503885454,67783835,515055444,30266251,878739865,528849214,726903343,30018018,1655128,486406041,349065536,966623595,121950188,710389056,292765450,623882873,584281857,375431446,569358036,13380020,539696852,507045214,693800402,14636851,626892508,627609774,945281201,50103279,65199107,377709957,2565345,959059053,40733036,138809815,602298641,388325907,390715716,901529933,161949277,19717790,477393470,346123676,560401387,950319214,972125537,251292561,166717656,704968704,534706207,381136932,972180770,32109945,653450218,306443168,724539070,95871000,484140328,923932791,84166880,548512434,494160245,31974766,321958990,298933068,203823543,218848814,345508165,159947667,738396872,721210269,983287415,224920240,456233538,45948307,306566476,442471557,676567516,144330547,254465966,962527963,6139868,906524998,716649568,286491931,411547743,985573261,781406894,36144631,330898272,217590352,23878870,338683257,63330780,396014195,551731890,916466062,292387750,511308492,125248328,514674636,72477136,499996903,344438010,501205405,121356879,121557859,558966494,101887611,880611418,126290849,294929416,486437436,83742723,862156676,195087223,416406570,43500064,399609177,50073670,567560644,16867381,608188219,590215591,526472444,789740668,722468616,450467552,921269367,210134877,66740649,162097518,363720630,107147626,677327505,32563788,838738578,389600116,124488487,421907409,799799247,125797756,951955022,547863182,319600116,662548465,749341560,339492912,786300483,885337790,751025045,716537896,557104274,222832198,76755065,970662764,643291936,20384285,148778122,635909924,504960127,9481545,442536937,982430598,856782450,857762593,151156818,812464303,386512895,777172668,945490022,619295601,440907576,515047682,692788895,46624231,929402909,471621863,186510364,501046775,602746116,466587291,115299571,809640203,166504429,61724740,966082257,968122079,537167012,144718696,335635268,375387185,972947056,26176865,867906067,981316223,100329579,257549936,107720578,131040025,218962000,100341620,666944445,618133422,235517946,537757001,470729231,9408447,6957429,969392265,764851713,818608027,564867107,489242540,131969064,239408453,146493671,102869035,988513988,21103124,138381891,852630914,9395167,138265538,44569690,403965605,254115068,359952571,261427198,55375024,827609217,376528500,827675438,134999778,198537614,425069638,614795944,124583669,667126214,171136289,599984468,148725942,113425733,966773151,695075655,972977552,538723137,528707807,852264610,88353358,836666407,922360471,575472051,485393647,868133823,514244021,70560350,496829306,793726406,138774125,795435389,589858926,767433308,257802252,53428296,321206426,889996871,746788120,18994703,416393565,470419960,460963113,79020393,950851305,532065808,101107526,447603283,26140518,50000616,132720644,547838122,45900343,86392684,888851772,828462050,470685780,633632559,883992218,965337980,196476775,502791986,869736335,884880863,661387544,358073714,688710882,19915022,497304400,188696676,739170560,839682603,430464184,732112323,677998998,373906982,510473930,131150323,718235417,170052310,561418591,866597666,465857086,727646018,774738508,629730773,878667973,320560370,769151914,77642236,410486723,125857875,607869986,684124501,246020847,759333632,418017481,200793830,838069951,889404362,732929014,164717684,96672583,71443927,900679572,902317479,867838086,838759556,949198784,675432772,193019540,24596741,80565763,947059709,876716177,83484772,614720091,849722298,516409936,320376825,624773324,163201216,586220093,93614262,855345339,533579555,127354660,994531717,229343018,627935739,981324015,438311145,826504805,142028839,17343834,25999202,822386251,433947043,286465067,753023073,937656140,951743294,491339402,659685277,665359656,752388463,9184105,531408729,2020430,745112305,918343056,419749781,43767450,953103454,522206983,760076570,374179634,797968800,219224663,219951367,903268682,674837731,136605110,55043705,347076656,751772140,388061679,37781592,133035810,402382143,410672998,168635928,733111503,84326660,524924756,340530794,50114081,246748321,101087268,107127077,686465531,937006411,562144804,980136253,595926612,22321923,940878792,427764283,452032803,665660582,160579382,618212642,566968486,447381041,585886518,575165109,769070394,855019243,495335024,94627527,266947509,286423758,58742710,593732997,306951548,678947142,483999083,697511723,113783135,531177624,412805989,658077313,557596119,692315103,673536675,744593388,993861047,694810563,812543602,364786119,687468426,819814922,374314902,130955851,597228160,275119042,393446903,559949608,799720502,949814188,74088143,244861297,598129605,186298206,875769494,204969120,352230052,465552832,56499981,993365849,754930943,583951103,258899909,321880319,124193218,754288620,732868099,495424348,595895995,153236935,620273792,55999606,380519234,973443650,137002704,294955122,711456756,57730174,401404552,160170237,977142146,813577791,566531466,544836842,202532686,205273107,166372267,987961653,327943367,301130967,282184968,38864600,155282090,426434103,718017660,805177705,120206766,118961491,871482458,167199066,999070564,997311833,710112396,292413193,938928993,662725773,227368400,7290787,922667808,298434069,407081938,736211202,848381647,251903627,53990752,977448408,518472284,622521309,968290757,431675933,977646365,905073358,941256205,328493633,605011972,101144859,282080436,74973854,660147036,983692228,231656321,59935036,158319609,145429830,402762524,361285524,189531799,535675870,645877444,525344301,156394090,788465280,761858970,59183954,5743473,479743752,45123957,336617908,65253558,145384267,784468830,958495455,951254616,513557775,628747132,733504284,95862339,545596323,82227971,173523576,920927784,118621759,604057675,35122934,339105969,725400423,540245342,342603478,732997139,516715981,814602777,820623414,77738064,666562850,292612129,194500473,499338977,24093963,220310505,289828685,450775977,662517401,227248912,146539618,520595195,795064487,5581375,109867735,858569372,825789589,651790340,326161033,410214487,845354717,917898645,747490114,79989626,853859738,334887312,689392575,946732460,26114597,614346369,11027585,450006031,606936861,240499577,512166985,876059719,787813401,543146852,509136745,486423567,643625018,530547587,561192365,211900931,891060591,651882406,519009226,56970915,318418999,931846447,92480805,132686363,764655933,823100861,559495431,756302251,9204542,874893388,512641107,254693585,700174624,772003655,762212989,773751768,432482191,289017620,58613473,7603894,890089863,162221017,84863254,953525526,26036499,656258352,51089650,463267328,505761321,383225799,365525018,221242037,120722902,410746077,396874681,981534563,829507734,865627592,548713966,733824922,189857911,574189313,755757620,445525913,826026349,336048366,82895752,659500608,856595067,855900159,268504707,688446780,876120002,800989782,453261609,843366554,69602878,229961509,640000810,541004425,215609577,945248150,849120191,927194400,7916746,498721064,169226985,722566845,953918708,546300501,972907960,516574040,576484037,668478242,272350768,111706019,335332433,728090281,444510739,589361038,196385702,765106653,15438735,780781505,115166296,717170925,813509511,418949506,832952476,779347917,997677966,421258786,990315790,32196858,552670518,659601329,401929267,34615585,963552405,44067386,551676865,346165956,271001347,699802320,957141268,666270177,23129381,833944938,634292644,240622578,224939723,783684319,658120960,143687601,185890779,470594846,105304821,331601419,504985168,430345632,94113928,224823704,981236633,910144096,58782469,907457441,208349893,338307041,182719409,63491853,955684459,951485078,91965315,620307012,259823077,12200788,840676029,740084368,165668130,38432976,136407041,21065316,295921413,772040417,587093345,737975097,74888785,230392353,291261330,113941797,257347633,209602773,920624731,320177282,773042839,47909301,698232860,349030812,28512258,316666925,756531209,916839423,917993714,990809728,743878236,504698196,49658169,819664856,147122934,379947550,309590319,724593330,7818820,362429,234850418,849010718,441786758,52052605,260761415,750462025,636773922,141272631,838152791,488717664,545807651,486534020,352524942,126801768,292010461,819684632,332014519,5505927,989296846,293695648,18313708,146802344,995768852,340013071,938678208,949770994,555148007,703591081,3316563,492856675,390688824,95051020,942143419,492380,271453228,852115346,727156957,145024869,624991094,675777959,552126508,313381269,369085639,82540715,573318199,792825082,22607186,440326739,135833389,969630740,477933744,836574206,520221911,756709818,416732170,866386901,71013378,668419961,440305648,781356952,403790859,464642693,999200759,245036973,610253912,948579490,4376749,131533601,363032753,490438544,758371822,639767409,120222534,945500758,445230484,155718440,170233965,674031951,478762532,88133662,84697960,529934337,991717850,181320583,968721966,236554655,574834566,508601487,80276949,387930105,973901021,234102513,370894687,629460815,636451161,11595798,262543687,640336471,887491558,442181822,456463734,767368832,174154120,135567626,590897871,49112747,242691890,851149577,882367972,583922869,784371071,669965011,638157234,768277298,410356653,294276454,42501915,10609532,73261623,799968030,815049990,539976295,115697843,60946766,775575121,12805004,51294684,407285050,209452361,333112472,924427753,960542273,992386390,325549059,862185704,328455750,322817460,842336476,729929686,147135869,158872586,642358259,507944122,562340207,969307180,334828118,49024086,107071532,107425785,57378524,933673943,594951372,663848772,128764839,280111475,549406101,836141054,682687188,65926442,510105998,389768140,800984208,359579391,431841879,619217140,269697196,255772933,660907284,876278482,962574426,994064931,974005304,632281825,11547419,596921481,208710961,964325976,367594723,1540689,710513415,235383516,425875638,128852415,959022729,430235568,184730505,297222551,372451735,28962787,884730396,486993744,843676691,987108143,808364904,369184,348381703,3839177,686495585,294640342,70421659,899290472,178033896,563948379,80566573,167694801,740954121,751221272,719557791,127377080,578366079,87703431,650761553,8185678,930715316,261431264,123712286,468220506,1961734,551587211,632329756,817123736,33686965,34116525,18301926,510308761,857143656,486100894,662910848,190440278,772096894,181797215,744046471,184740194,460065574,380973018,10256750,586505490,447830700,907875812,590438927,778091880,362300577,862636972,470466085,881680919,774041333,4233852,877347369,747489059,62258241,342698976,983526956,955918533,797620924,21945094,256986152,576642547,37588518,390029808,110892412,545941466,588079078,918299030,679804799,866254753,351990658,382520099,596748422,595075642,397949593,867711371,856544198};
//    Solution S;
//    S.totalHammingDistance(nums);
//}